public class UsePreorderAndInorderCreateTree {
    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public  int preorderIndex;
    public TreeNode buildTree(int[] preorder, int[] inorder) {

        return buildTreeChild(preorder,inorder,0,inorder.length - 1);
    }

    public TreeNode buildTreeChild(int[] preorder,int[] inorder,int ib,int ie) {
        if (ib > ie) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[preorderIndex]);
        int rootindex = findval(inorder,ib,ie,preorder[preorderIndex]);
        preorderIndex++;

        root.left = buildTreeChild(preorder,inorder,ib,rootindex - 1);
        root.right = buildTreeChild(preorder,inorder,rootindex + 1,ie);

        return root;
    }

    public int findval(int[] inorder,int ib,int ie,int val){

        for (int i = ib; i <= ie; i++) {
            if (inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }

}
